package com.lile.array;

/**
 * 基本查找：数组元素无序 二分查找：数组元素有序（折半查找）
 * 
 * 如果数组本身是无序的，不能直接使用二分查找；如果对数组先排序，再二分查找，无法得到正确的索引，因为这样就改变了数组中原始的索引位置。
 * 
 * @author LiLe
 *
 */
public class ArraySearch {

	public static void main(String[] args) {
		int[] arr = { 13, 24, 57, 69, 80 };
		int index = getIndex(arr, 57);
		System.out.println(index);
	}

	public static int getIndex(int[] arr, int value) {
		int minIndex = 0;
		int maxIndex = arr.length - 1;
		int middleIndex = (minIndex + maxIndex) / 2;

		while (value != arr[middleIndex]) {
			if (value > arr[middleIndex]) {
				minIndex = middleIndex + 1;
			} else if (value < arr[middleIndex]) {
				maxIndex = middleIndex - 1;
			}

			if (maxIndex < minIndex) {
				return -1;
			}

			middleIndex = (minIndex + maxIndex) / 2;
		}
		return middleIndex;
	}
}
